#include<iostream> 
#include "stdlib.h"

using namespace std;

// 不改变原数组
// 空间复杂度O(1) 
int getCounter(const int * arr, int length, int start, int end){
	int count = 0;
	for ( int i = 0 ; i < length; i++){
		if ( arr[i] >= start && arr[i] <= end)
			++count;
	}
	return count;
}

int duplication(int arr[] , int n){
	int start = 1;
	int end = n-1;
	while ( end >= start){
		cout << end << endl;
		int middle = (( end - start) >> 1) + start;
		int count = getCounter(arr, n, start, middle);

		if ( start == end ){
			if ( count > 1 ){
				return start;
			}else {
				// 无重复数字
				break;
			}
		}else {
			if ( count > (middle-start + 1) ){
				// 左边有重复数字
				end = middle;
			}else {
				// 右边有重复数字
				start = middle + 1;
			}
		}
	}
	return -1;
}


void print(int arr[], int n){
	for (int i=0; i< n; i++){
		cout << arr[i] << endl;
	}
}


int main(void) {
	int arr[] = {2,3,1,0,2,5,3};
	int tmp = duplication(arr, 7);
	cout << "重复数字: " << tmp << endl;
	cout << "---------" << endl;
	print(arr, 7);
	return 0;
}

// 参考链接： https://www.cnblogs.com/hiddenfox/p/3408931.html
// 优秀代码： https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.